#include "KNNMath.h"

void SpawnArray(int** pArray, const int IndexA, const int IndexB)
{
	int* Temp;
	Temp = pArray[IndexA];
	pArray[IndexA] = pArray[IndexB];
	pArray[IndexB] = Temp;
}

void MiddleSplit(int** pArray, const int Start, const int Middle, const int End)
{
	int Left = Start;
	int Right = End;
	while (Right > Left)
	{
		const int v = *(pArray[Right]);
		int i = Left - 1;
		int j = Right;
		while(1)
		{
			while (*(pArray[++i]) < v)
				;
			while (*(pArray[--j]) > v && j > Left)
				;
			if (i >= j)
				break;
			SpawnArray(pArray, i, j);
		}

		SpawnArray(pArray, i, Right);
		if (i >= Middle)
			Right = i - 1;
		if (i <= Middle)
			Left = i + 1;
	}
}

void BalanceSegment(int** pArray, int** pDestArray, int Index, int Start, int End)
{
	// Compute the new median
	int Median = 1;
	while ((4 * Median) <= (End - Start + 1))
		Median += Median;

	if ((3 * Median) <= (End - Start + 1))
	{
		Median += Median;
		Median += Start - 1;
	}
	else
	{
		Median = End - Median + 1;
	}

	MiddleSplit(pArray, Start, Median, End);
	pDestArray[Index] = pArray[Median];

	if (Median > Start)
	{
		if (Start < Median - 1)
		{
			BalanceSegment(pArray, pDestArray, 2*Index, Start, Median - 1);
		}
		else
		{
			pDestArray[2*Index] = pArray[Start];
		}
	}

	if (Median < End)
	{
		if (Median + 1 < End)
		{
			BalanceSegment(pArray, pDestArray, 2*Index+1, Median+1, End);
		}
		else
		{
			pDestArray[2*Index + 1] = pArray[End];
		}
	}
}